#include "Array.h"

// 构造函数
template <class T>
DynamicArray<T>::DynamicArray() : m_head(nullptr), m_tail(nullptr), m_size(0)
{
}

template <class T>
DynamicArray<T>::DynamicArray(std::initializer_list<T> l) : m_size(l.size())
{
    auto j = l.begin();
    m_head = new Node(*j++, nullptr, nullptr);

    Node *p = m_head;
    for (int i = 1; i < m_size; i++)
    {
        p->next = new Node(*j++, p, nullptr);
        p = p->next;
    }
    m_tail = p;
}

template <class T>
DynamicArray<T>::DynamicArray(const DynamicArray<T> &arr) : m_size(arr.m_size)
{
    m_head = (arr.empty() ? nullptr : new Node(arr[0], nullptr, nullptr));

    Node *p = m_head;
    for (int i = 1; i < m_size; i++)
    {
        p->next = new Node(arr[i], p, nullptr);
        p = p->next;
    }
    m_tail = p;
}

// 拷贝赋值
template <class T>
void DynamicArray<T>::operator=(const DynamicArray<T> &arr)
{
    // 首先清空
    this->clear();

    // 然后依次推入
    Node *node = arr.m_head;
    while (node != nullptr)
    {
        this->push_back(node->value);
        node = node->next;
    }
}

// 获取元素，如果超出数组范围，就创建新的节点达到该范围
template <class T>
T &DynamicArray<T>::operator[](int i)
{
    DEBUG_ASSERT(i >= 0, DEBUG_OUT_OF_RANGE, this->operator[](0))

    // 如果数组是空的，就先初始化
    if (m_size == 0)
    {
        m_head = new Node(T(), nullptr, nullptr);
        m_tail = m_head;
        m_size++;
    }

    // 如果在范围内，就从头部出发寻找
    Node *p = nullptr;
    if (i < m_size)
    {
        p = m_head;
        while (i > 0)
        {
            p = p->next;
            i--;
        }
    }
    // 如果超出范围，直接从尾部出发
    else
    {
        p = m_tail;
        // 注意要先减去数组范围
        i -= m_size - 1;
        while (i > 0)
        {
            p->next = new Node(T(), p, nullptr);
            p = p->next;
            m_size++;
            i--;
        }
    }

    // 如果这是最后一个节点，那么就作为尾部节点
    if (p->next == nullptr)
        m_tail = p;
    return p->value;
}

// 在数组范围内获取元素
template <class T>
T DynamicArray<T>::operator[](int i) const
{
    DEBUG_ASSERT(i < m_size && i >= 0, DEBUG_OUT_OF_RANGE, T())
    Node *p = m_head;
    while (i > 0)
    {
        p = p->next;
        i--;
    }
    return p->value;
}

// 获得头部元素
template <class T>
T DynamicArray<T>::front() const
{
    return m_head->value;
}

// 获得尾部元素
template <class T>
T DynamicArray<T>::back() const
{
    return m_tail->value;
}

// 在 i 位置插入元素
template <class T>
void DynamicArray<T>::insert(int i, T value)
{
    // 如果超出范围，就直接调用引用修改
    if (i >= m_size)
    {
        operator[](i) = value;
        return;
    }

    Node *q = new Node(value, nullptr, nullptr);
    if (i == 0)
    {
        q->next = m_head;

        if (m_head != nullptr)
        {
            m_head->prev = q;
            m_head = q;
        }
        else
        {
            // 数组是空
            m_head = q;
            m_tail = q;
        }
    }
    else
    {
        // 获取前一个位置的元素和后一个位置
        Node *prev = m_head;
        while (i - 1 > 0)
        {
            i--;
            prev = prev->next;
        }
        Node *next = prev->next;

        // 重新建立连接
        prev->next = q;
        q->prev = prev;
        q->next = next;

        // 如果 q 不是尾部
        if (next != nullptr)
            next->prev = q;
        else
            m_tail = q;
    }
    m_size++;
}

// 尾部推入元素
template <class T>
void DynamicArray<T>::push_back(T value)
{
    Node *q = new Node(value, nullptr, nullptr);

    // 如果数组是空，直接作为头尾节点
    if (m_size == 0)
    {
        m_head = q;
        m_tail = q;
    }
    else
    {
        q->prev = m_tail;
        m_tail->next = q;
        m_tail = q;
    }
    m_size++;
}

// 头部推入元素
template <class T>
void DynamicArray<T>::push_front(T value)
{
    Node *q = new Node(value, nullptr, nullptr);

    // 如果数组是空，直接作为头尾节点
    if (m_size == 0)
    {
        m_head = q;
        m_tail = q;
    }
    else
    {
        q->next = m_head;
        m_head->prev = q;
        m_head = q;
    }
    m_size++;
}

// 弹出最后一个元素
template <class T>
T DynamicArray<T>::pop_back()
{
    DEBUG_ASSERT(m_size > 0, DEBUG_OUT_OF_RANGE, T())
    T value;

    if (m_size == 1)
    {
        value = m_head->value;
        delete m_head;
        m_head = nullptr;
        m_tail = nullptr;
    }
    else
    {
        value = m_tail->value;
        m_tail = m_tail->prev;
        delete m_tail->next;
        m_tail->next = nullptr;
    }
    m_size--;

    return value;
}

// 弹出第一个元素
template <class T>
T DynamicArray<T>::pop_front()
{
    DEBUG_ASSERT(m_size > 0, DEBUG_OUT_OF_RANGE, T())
    T value;

    if (m_size == 1)
    {
        value = m_head->value;
        delete m_head;
        m_head = nullptr;
        m_tail = nullptr;
    }
    else
    {
        value = m_head->value;
        m_head = m_head->next;
        delete m_head->prev;
        m_head->prev = nullptr;
    }
    m_size--;

    return value;
}

// 找到元素
template <class T>
int DynamicArray<T>::find(T value) const
{
    int index = 0;
    Node *p = m_head;
    while (p != nullptr)
    {
        if (p->value == value)
            return index;
        p = p->next;
        index++;
    }
    return -1;
}

// 删除指定元素
template <class T>
bool DynamicArray<T>::kill(T value)
{
    Node *p = m_head;
    while (p != nullptr)
    {
        if (p->value == value)
        {
            // 头尾的特殊情况
            if (p == m_head)
            {
                this->pop_front();
                return true;
            }
            if (p == m_tail)
            {
                this->pop_back();
                return true;
            }

            // 其余情况正常删除
            Node *prev = p->prev;
            Node *next = p->next;
            prev->next = next;
            next->prev = prev;
            delete p;

            m_size--;
            return true;
        }
        p = p->next;
    }
    return false;
}

// 删除指定位置的元素
template <class T>
T DynamicArray<T>::remove(int i)
{
    DEBUG_ASSERT(i < m_size, DEBUG_OUT_OF_RANGE, T())

    // 先找到节点
    Node *p = m_head;
    while (i > 0)
    {
        p = p->next;
        i--;
    }

    // 头尾的特殊情况
    if (p == m_head)
        return this->pop_front();
    if (p == m_tail)
        return this->pop_back();

    // 其余情况正常删除
    Node *prev = p->prev;
    Node *next = p->next;
    prev->next = next;
    next->prev = prev;

    T value = p->value;
    delete p;
    m_size--;
    return value;
}

// 清空数组
template <class T>
void DynamicArray<T>::clear()
{
    Node *p = m_head;
    Node *q = nullptr;
    while (p != nullptr)
    {
        q = p;
        p = p->next;
        delete q;
    }

    // 初始化成员变量
    m_head = nullptr;
    m_tail = nullptr;
    m_size = 0;
}

// 获得指定的节点
template <class T>
typename DynamicArray<T>::Node *DynamicArray<T>::node(int i) const
{
    DEBUG_ASSERT(i < m_size, DEBUG_OUT_OF_RANGE, nullptr)
    Node *p = m_head;
    while (i > 0)
    {
        p = p->next;
        i--;
    }
    return p;
}

// 在指定节点处插入元素
template <class T>
typename DynamicArray<T>::Node *DynamicArray<T>::insert(Node *node, T value)
{
    Node *q = new Node(value, node->prev, node);

    // 如果是头部节点，就需要修改头部
    if (node == m_head)
        m_head = q;
    else
        node->prev->next = q;

    node->prev = q;
    m_size++;

    return q;
}

// 移除指定节点的元素
template <class T>
void DynamicArray<T>::remove(Node *node)
{
    T value = node->value;

    // 头尾的特殊情况
    if (node == m_head)
    {
        this->pop_front();
        return;
    }
    if (node == m_tail)
    {
        this->pop_back();
        return;
    }

    // 其余情况正常删除
    Node *prev = node->prev;
    Node *next = node->next;
    prev->next = next;
    next->prev = prev;

    delete node;
    m_size--;
}

// 析构函数
template <class T>
DynamicArray<T>::~DynamicArray()
{
    clear();
}